package top.datacluster.basic.algorithm.leetcode.dynamic;

import java.util.Arrays;

public class GatherCoin {

    public static int gather(int target){
        int[] coins = new int[]{1, 3, 5};

        int[] result = new int[target + 1];

        result[0] = 0;
        result[1] = 1;

        for (int i = 2; i <= target; i++){
            int[] temp = new int[3];
            Arrays.fill(temp, -1);
            for (int j = 0; j < coins.length; j++){
                if (i - coins[j] >= 0) {
                    temp[j] = i - coins[j];
                }
            }
            int k = 0;
            if (temp[1] == -1){
                k = result[temp[0]] + 1;
            }else if (temp[2] == -1){
                k = Math.min(result[temp[0]] + 1, result[temp[1]] + 1);
            }else{
                k = Math.min(Math.min(result[temp[0]] + 1, result[temp[1]] + 1), result[temp[2]] + 1);
            }
            result[i] = k;
        }

        for (int i = 0 ; i < result.length; i++){
            System.out.println("当目标是" + i + "，需要" + result[i] + "个硬币");
        }
        return result[target];

    }

    public static void main(String[] args) {
        System.out.println(gather(100));
    }
}
